package fanruan;

import java.util.ArrayList;

/**
 * @author blh
 * @date 2024年06月28日 10:58
 */

public class test1 {

    static ArrayList<Integer> res = new ArrayList<>();

    public static ArrayList<Integer> MinimumK(int N) {
        // 感觉是回溯算法
        backTrace(N, new ArrayList<>(), 0);
        res.sort((o1, o2) -> Integer.compare(o2, o1));
        System.out.println(N);
        return res;
    }

    private static void backTrace(int target, ArrayList<Integer> curList, int curSum) {

        if (curSum > target) {
            return;
        }

        if ((target - curSum) < 8 && (target - curSum) >= 0) {
            ArrayList<Integer> temp = new ArrayList<>(curList);
            for (int i = 0; i < target - curSum; i++) {
                temp.add(1);
            }
            if (res.isEmpty()) {
                res = new ArrayList<>(temp);
            } else {
                if (res.size() > temp.size()) {
                    res = new ArrayList<>(temp);
                }
            }
            return;
        }
        int gap = target - curSum;
        int tri = get3(gap);
        for (int i = tri; i >= 2; i--) {
            if (!res.isEmpty() && curList.size() > res.size()) {
                continue;
            }
            curList.add(i);
            backTrace(target, curList, curSum + (i * i * i));
            curList.remove(curList.size() - 1);
        }

    }

    private static int get3(int gap) {
        int tri = 1;
        for (int i = 1; i < Math.sqrt(gap); i++) {
            if ((i * i * i) <= gap) {
                tri = i;
            } else {
                break;
            }
        }
        return tri;
    }

    public static void main(String[] args) {
        ArrayList<Integer> integers = MinimumK(42);
    }
}
